SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Code linéaire</title>

</head>

<h1 id="firstHeading" class="firstHeading mw-first-heading">Code linéaire</h1>

</header>

</div>

<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="fr" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="fr" dir="ltr">En <a href="Math%C3%A9matiques" title="Mathématiques">mathématiques</a>, plus précisément en <a href="Th%C3%A9orie_des_codes" title="Théorie des codes">théorie des codes</a>, un code linéaire est un <a href="Code_correcteur" title="Code correcteur">code correcteur</a> ayant une certaine propriété de linéarité.

Plus précisément, un tel code est structuré comme un <a href="Sous-espace_vectoriel" title="Sous-espace vectoriel">sous-espace vectoriel</a> d'un <a href="Espace_vectoriel_de_dimension_finie" title="Espace vectoriel de dimension finie">espace vectoriel de dimension finie</a> sur un <a href="Corps_fini" title="Corps fini">corps fini</a>. L'<a href="Espace_vectoriel_fini" title="Espace vectoriel fini">espace vectoriel fini</a> utilisé est souvent F2n le terme usuel est alors celui de code linéaire binaire. Il est décrit par trois paramètres [n, k, δ] . n décrit la dimension de l'espace qui le contient. Cette grandeur est appelée longueur du code. k représente la dimension du code, correspondant à la taille des mots une fois décodés et δ décrit la distance minimale, au sens de <a href="Distance_de_Hamming" title="Distance de Hamming">Hamming</a> entre chaque mot du code.

Les codes linéaires représentent l'essentiel des codes correcteurs utilisés dans l'industrie. Cette approche couvre en particulier les codes proposant une simple détection, une nouvelle émission est alors demandée. D'autres codes permettent une correction des altérations à l'aide d'une gestion fine de la redondance.

Rappel: F2 est l'unique <a href="Corps_commutatif" title="Corps commutatif">corps</a> à deux éléments et F2n est un espace vectoriel de dimension n. Si le corps de base est Fd, le corps contenant d éléments, le terme consacré est code linéaire de base d. La théorie des corps finis assure que d est une <a href="Nombre_primaire" title="Nombre primaire">puissance d'un nombre premier</a> et qu'il existe un unique corps possédant ce cardinal.

<div class="mw-heading mw-heading2"><h2 id="Approche_intuitive">Approche intuitive</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Code_correcteur"><a href="Code_correcteur" title="Code correcteur">Code correcteur</a></h3></div>

Un code linéaire est un cas particulier de <a href="Code_correcteur" title="Code correcteur">code correcteur</a>. L'objectif est de permettre la correction d'erreurs après la transmission d'un <a href="Message" title="Message">message</a>. Cette correction est permise grâce à l'ajout d'informations redondantes. Le message est <a href="Plongement" title="Plongement">plongé</a> dans un ensemble plus grand, la différence de taille contient la redondance. Un exemple simple est celui du <a href="Code_de_r%C3%A9p%C3%A9tition" title="Code de répétition">code de répétition</a>, le message est, par exemple, envoyé trois fois, le décodage se fait par vote. Ici, l'ensemble plus grand est de dimension triple à celle du message initial.

Rappelons les éléments de base de la formalisation. Il existe un ensemble E constitué de <a href="Suite_(math%C3%A9matiques)" title="Suite (mathématiques)">suites</a> de longueur k, c’est-à-dire qu'à partir du rang k, toutes les valeurs de la suite sont nulles, et à valeur dans un alphabet. Ces éléments sont l'espace des messages que l'on souhaite communiquer. Pour munir le message de la redondance souhaitée, il existe une <a href="Application_(math%C3%A9matiques)" title="Application (mathématiques)">application</a> φ <a href="Injection_(math%C3%A9matiques)" title="Injection (mathématiques)">injective</a> de E à valeurs dans F, l'espace des suites de longueur n à valeurs dans un alphabet. La fonction φ est appelée encodage, φ(E) est appelé le code, un élément de φ(E) mot du code, n la longueur du code et k la dimension du code.

Pour permettre d'utiliser la puissance des outils mathématiques, il peut être judicieux d'utiliser des <a href="Structure_(math%C3%A9matiques)" title="Structure (mathématiques)">structures</a> <a href="Structure_alg%C3%A9brique" title="Structure algébrique">algébriques</a>. les alphabets de E et F sont choisis comme un même <a href="Corps_fini" title="Corps fini">corps fini</a>. Les éléments de E (resp. F) sont les suites finies de longueur k (resp. n), E et F héritent naturellement d'une structure d'<a href="Espace_vectoriel_de_dimension_finie" title="Espace vectoriel de dimension finie">espace vectoriel de dimension finie</a> et d'une <a href="Base_canonique" title="Base canonique">base canonique</a>, celle de l'espace des suites finies à valeurs dans un corps. L'application encodage est choisie <a href="Application_lin%C3%A9aire" title="Application linéaire">linéaire</a>.

L'espace F est muni d'une <a href="Distance_(math%C3%A9matiques)" title="Distance (mathématiques)">distance</a> appelée <a href="Distance_de_Hamming" title="Distance de Hamming">distance de Hamming</a> dérivant d'une <a href="Pseudo-norme" class="mw-redirect" title="Pseudo-norme">pseudo-norme</a>[réf. nécessaire], le poids de Hamming. Le poids de Hamming p d'un point de F correspond au nombre de ses coordonnées non nulles. La distance de Hamming entre deux éléments de F est le poids au sens de Hamming de leur différence.

<div class="mw-heading mw-heading3"><h3 id="Domaine_d'application">Domaine d'application</h3></div>

Les codes linéaires correspondent à une très large majorité de type de codes correcteurs. Ils sont utilisés pour la détection d'altérations, avec comme méthode de correction associée une demande de retransmission, la technique utilisée la plus usuelle est alors la <a href="Somme_de_contr%C3%B4le" title="Somme de contrôle">somme de contrôle</a>. Elles sont utilisés dans une multitude de situations, depuis quelques erreurs isolées à de vastes altérations ou des phénomènes d'effacements.

Si le cadre utilisé est largement employé, il ne répond néanmoins pas à l'intégralité des besoins. On peut citer deux grands sujets, peu traités par la théorie des codes linéaires. Un bon code répond à un critère d'optimalité, il est dit parfait. Le cadre de la théorie des codes linéaires offre des critères pour valider cette optimalité. En revanche, il ne propose pas de méthode pour concevoir ce type de code.

Une méthode générale pour la correction des erreurs est disponible, le <a href="D%C3%A9codage_par_syndrome" title="Décodage par syndrome">décodage par syndrome</a>. Cette méthode consiste à créer une table associant à chaque erreur, sa solution. La table croît exponentiellement avec le nombre de lettres susceptible d'être erronées. Dans le cas d'une large capacité de correction, cette approche n'est plus opérationnelle.

La théorie des codes cycliques, utilisant largement les propriétés des corps finis répond à ces deux besoins. Un code cyclique est un code linéaire possédant une structure algébrique supplémentaire.

<div class="mw-heading mw-heading2"><h2 id="Définitions">Définitions</h2></div>

<ul><li>Soit p un <a href="Nombre_premier" title="Nombre premier">nombre premier</a>, d une puissance de p, n un entier strictement positif et k un entier plus petit que n. Un code linéaire C de dimension k et de longueur n est un <a href="Sous-espace_vectoriel" title="Sous-espace vectoriel">sous-espace vectoriel</a> de Fdn de <a href="Dimension_d'un_espace_vectoriel" title="Dimension d'un espace vectoriel">dimension</a> k. Si d est égal à deux, le code est dit <a href="Syst%C3%A8me_binaire" title="Système binaire">binaire</a>. Sinon, on parle de code linéaire de base d.</li></ul>

Ici, Fd désigne l'unique corps à d éléments (cf l'article <a href="Corps_fini" title="Corps fini">corps fini</a>). On remarque que l'espace vectoriel des suites à valeurs dans Fd est identifié à Fdn. L'espace vectoriel Fdn est muni de la <a href="Distance_de_Hamming" title="Distance de Hamming">distance de Hamming</a>.

Comme pour les autres codes correcteurs, la notion de paramètres s'applique. Cependant, pour tenir compte de la structure d'espace vectoriel, elle est un peu modifiée:

<ul><li>Les paramètres d'un code sont notés [n, k, δ] ou δ désigne la distance minimale entre deux points du code.</li></ul>

La définition de paramètre pour les codes linéaires n'est donc pas compatible avec celle, plus générique utilisées pour les codes correcteurs. Pour cette raison, traditionnellement les paramètres d'un code linéaire sont notés [n, k, δ] et ceux d'un code correcteur général {n, M, δ}.

Comme précédemment, il existe une application d'encodage : φ.

<ul><li>L'application d'encodage φ d'un code linéaire est une application linéaire injective de Fdk dans Fdn.</li></ul>

<ul><li>La <a href="Matrice_(math%C3%A9matiques)" title="Matrice (mathématiques)">matrice</a> G de φ dans les bases canoniques est dite <a href="Matrice_g%C3%A9n%C3%A9ratrice" title="Matrice génératrice">matrice génératrice</a> du code C. Elle vérifie l'égalité suivante :</li></ul>

</mrow>

</mrow>

</mrow>

</msubsup>

</mrow>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \forall x\in \mathbb {F} _{d}^{k}\quad G.x=\varphi (x)\in C\subset \mathbb {F} _{d}^{n}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e05bd77e516d19c6e86dcfa3fcaba2383b543b6c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:32.59ex; height:3.176ex;" alt="{\displaystyle \forall x\in \mathbb {F} _{d}^{k}\quad G.x=\varphi (x)\in C\subset \mathbb {F} _{d}^{n}}" loading="lazy"></center>

Le contrôle permettant la vérification et les éventuelles corrections est donné par une application linéaire h de Fdn dans Fdn-k ayant pour <a href="Noyau_(alg%C3%A8bre)" title="Noyau (algèbre)">noyau</a> C. La théorie de l'<a href="Alg%C3%A8bre_lin%C3%A9aire" title="Algèbre linéaire">algèbre linéaire</a> montre qu'une telle application existe, il suffit par exemple de considérer un <a href="Projecteur_(math%C3%A9matiques)" title="Projecteur (mathématiques)">projecteur</a> sur un <a href="Sous-espace_suppl%C3%A9mentaire" title="Sous-espace supplémentaire">sous-espace supplémentaire</a> de C parallèlement à C.

<ul><li>La matrice H de h dans les bases canoniques est dite <a href="Matrice_de_contr%C3%B4le" title="Matrice de contrôle">matrice de contrôle</a> du code C. Elle vérifie les propriétés suivantes :</li></ul>

</mrow>

</mrow>

</mrow>

</msubsup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \forall x\in \mathbb {F} _{d}^{n}\quad H.^{t}x=0\;\Leftrightarrow \;x\in C}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b7b804dddf0b755cb60a5a9f993bd2818fbb108e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:30.779ex; height:3.009ex;" alt="{\displaystyle \forall x\in \mathbb {F} _{d}^{n}\quad H.^{t}x=0\;\Leftrightarrow \;x\in C}" loading="lazy"></center>

Le terme de matrice de parité est aussi utilisé pour désigner la matrice de contrôle.

Remarque : Ces notations sont utilisées dans le reste de l'article.

<div class="mw-heading mw-heading2"><h2 id="Propriétés">Propriétés</h2></div>

Toutes les propriétés de l'<a href="Alg%C3%A8bre_lin%C3%A9aire" title="Algèbre linéaire">algèbre linéaire</a> s'appliquent aux codes linéaires. Le code est ainsi à la fois plus facile à implémenter et à décoder. De plus les outils de génération d'espace vectoriel comme l'<a href="Espace_dual" title="Espace dual">espace dual</a> ou le <a href="Produit_tensoriel" title="Produit tensoriel">produit tensoriel</a> permettent de concevoir des nouveaux codes, parfois plus adaptés aux contraintes industrielles.

<div class="mw-heading mw-heading3"><h3 id="Matrice_génératrice"><a href="Matrice_g%C3%A9n%C3%A9ratrice" title="Matrice génératrice">Matrice génératrice</a></h3></div>

L'application d'encodage est linéaire, elle se représente donc et se calcule grâce à sa <a href="Matrice_g%C3%A9n%C3%A9ratrice" title="Matrice génératrice">matrice génératrice</a>. Un code est entièrement défini par sa matrice génératrice, de dimension k x n. De plus comme les propriétés de son code ne dépendent que de la géométrie φ(E). Si f est un isomorphisme de E, le code défini par l'application φof est le même que celui de φ. Ce qui donne lieu à la définition suivante :

<ul><li>Deux codes sur un même alphabet Fd de longueur k définis par deux matrices génératrices G et G' tel qu'il existe une <a href="Matrice_carr%C3%A9e" class="mw-redirect" title="Matrice carrée">matrice carrée</a> inversible P d'ordre k vérifiant G =G'.P sont dits équivalents.</li></ul>

Il existe une forme particulièrement simple pour la matrice G :

<ul><li>Un code linéaire dont la matrice génératrice possède pour k premières lignes une <a href="Matrice_identit%C3%A9" title="Matrice identité">matrice identité</a> d'ordre k est dit code systématique.</li></ul>

L'article associé à ce paragraphe démontre une propriété importante :

<ul><li>Tout code linéaire est équivalent à un code systématique.</li></ul>

Cette écriture accélère et simplifie l'encodage et le décodage. La matrice prend alors la forme suivante :

<mrow>

</mrow>

<msub>

</mrow>

</msub>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G={I_{k} \choose C}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ebf785c9cabdacc05b1e9ddd18c94fa07c892145.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:10.458ex; height:6.176ex;" alt="{\displaystyle G={I_{k} \choose C}}" loading="lazy"></center>

Les coordonnées de la matrice C correspondent à la redondance, leur objectif est la détection et la correction d'erreurs éventuelles:

<ul><li>Les n - k dernières coordonnées d'un mot du code systématique sont dites bits de contrôle ou parfois somme de contrôle.</li></ul>

<div class="mw-heading mw-heading3"><h3 id="Matrice_de_contrôle"><a href="Matrice_de_contr%C3%B4le" title="Matrice de contrôle">Matrice de contrôle</a></h3></div>

Dans le cas linéaire, le code est un sous-espace vectoriel de dimension k. Il existe alors une application linéaire <a href="Surjection" title="Surjection">surjective</a> de F dans un espace de dimension n - k ayant pour noyau exactement le code :

<ul><li>Une <a href="Matrice_de_contr%C3%B4le" title="Matrice de contrôle">matrice de contrôle</a> d'un code φ(E) est une matrice H de dimension nxn - k tel que :</li></ul>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x\in \varphi (E)\Leftrightarrow H.^{t}x=0}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/cda6fe6d8374352ba24df6e579bf13c3a2129db7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:22.404ex; height:3.009ex;" alt="{\displaystyle x\in \varphi (E)\Leftrightarrow H.^{t}x=0}" loading="lazy"></center>

Dans le cas d'un code systématique, l'expression de la matrice génératrice offre immédiatement celle d'une matrice de contrôle.

<ul><li>Dans le cas d'un code systématique, si G est l'expression d'une matrice génératrice alors l'expression suivante est celle d'une matrice de contrôle :</li></ul>

<mrow>

</mrow>

<msub>

</mrow>

</msub>

</mfrac>

</mrow>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle si\quad G={I_{k} \choose C}\quad alors\quad H=(-C\;I_{n-k})\;}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c29b20720ab5dc4aac62c0b82e43c27e411de89b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:40.721ex; height:6.176ex;" alt="{\displaystyle si\quad G={I_{k} \choose C}\quad alors\quad H=(-C\;I_{n-k})\;}" loading="lazy"></center>

Ici, Ik désigne la matrice carrée identité d'ordre k.

Cette matrice offre une manière relativement simple de calculer la distance minimale :

<ul><li>La distance minimale δ d'un code linéaire est égale à la dimension du plus petit sous-espace vectoriel S de F généré par des éléments de la base canonique et tel que la restriction de la matrice de contrôle à S soit non <a href="Injection_(math%C3%A9matiques)" title="Injection (mathématiques)">injective</a>.</li></ul>

<div class="mw-heading mw-heading3"><h3 id="Distance_de_Hamming"><a href="Distance_de_Hamming" title="Distance de Hamming">Distance de Hamming</a></h3></div>

Dans le cas d'un code linéaire, la <a href="Distance_de_Hamming" title="Distance de Hamming">distance de Hamming</a> s'exprime comme une distance issue d'une pseudo-norme. Le <a href="Poids_de_Hamming" class="mw-redirect" title="Poids de Hamming">poids de Hamming</a>, qui à un code associe le nombre de coordonnées non nulles, joue ici le rôle de pseudo-norme.

<ul><li>Si ω désigne le poids de Hamming pour un code linéaire C, alors la distance de Hamming d est définie par la formule suivante:</li></ul>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \forall x,y\in C\quad d(x,y)=\omega (x-y)\;}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e58d8552b6319dba94161cf6a78ca73e59ef813d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:30.61ex; height:2.843ex;" alt="{\displaystyle \forall x,y\in C\quad d(x,y)=\omega (x-y)\;}" loading="lazy"></center>

La linéarité de la structure sous-jacente introduit une propriété directe:

<ul><li>La distance minimale δ entre deux points du code est égale au minimum du poids des mots du code non nuls.</li></ul>

Pour s'en convaincre, il suffit de remarquer que si x et y sont deux mots du code, alors leur différence est aussi un mot du code.

<div class="mw-heading mw-heading3"><h3 id="Borne_de_Singleton_et_code_MDS">Borne de Singleton et code MDS</h3></div>

Le nombre maximum d'erreurs assurément corrigibles t découle directement de la distance minimale δ. En effet, t est le plus grand entier strictement inférieur à δ/2. La situation idéale est celle où les <a href="Boule_(math%C3%A9matiques)" class="mw-redirect" title="Boule (mathématiques)">boules</a> fermées de centre les mots du code et de rayon t forment une <a href="Partition_(math%C3%A9matiques)" class="mw-redirect" title="Partition (mathématiques)">partition</a> de F. On parle alors de parfait.

<ul><li>La majoration suivante est vérifiée pour tous les codes linéaires. Elle se nomme borne de Singleton:</li></ul>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n-k\geq \delta -1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/912ed5d6bfbbea7a32699fee797eb60da55507de.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:13.596ex; height:2.509ex;" alt="{\displaystyle n-k\geq \delta -1}" loading="lazy"></center>

Si la borne de Singleton est atteinte, le code est dit MDS.

La structure linéaire du code donne naturellement naissance à la notion de code dual. La <a href="Forme_bilin%C3%A9aire_sym%C3%A9trique" title="Forme bilinéaire symétrique">forme bilinéaire symétrique</a> canonique permet ainsi de définir le code dual de C.

<ul><li>Le code dual d'un code linéaire C de dimension k est le sous-espace orthogonal de C dans l'espace muni de sa forme bilinéaire symétrique canonique. C'est un code de même longueur n et de dimension n - k. Il est souvent noté <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \scriptstyle {C^{\perp }}}">

<msup>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \scriptstyle {C^{\perp }}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/01204c048728c513baa4e8ca822da00e24a44a4f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.474ex; height:2.176ex;" alt="{\displaystyle \scriptstyle {C^{\perp }}}" loading="lazy">. Un code est dit autodual s'il est égal à son dual.</li></ul>

Dans le cas d'un code systématique, auquel il est toujours possible de se ramener, la matrice de contrôle de C devient une matrice génératrice de son dual. Il suffit alors de réordonnancer la base pour obtenir un code systématique. De même une matrice génératrice de C est une matrice de contrôle de son dual.

Il est possible de calculer la distance minimale de <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \scriptstyle C^{\bot }}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \scriptstyle C^{\bot }}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/3e66843f3d59dc4f7768effbd1e644d8528a9c4d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.474ex; height:2.176ex;" alt="{\displaystyle \scriptstyle C^{\bot }}" loading="lazy"> à partir de <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4fc55753007cd3c18576f7933f6f089196732029.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.766ex; height:2.176ex;" alt="{\displaystyle C}" loading="lazy">, toutefois il n'est pas suffisant de connaitre celle de <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4fc55753007cd3c18576f7933f6f089196732029.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.766ex; height:2.176ex;" alt="{\displaystyle C}" loading="lazy"> : il faut connaitre le <a href="Polyn%C3%B4me" title="Polynôme">polynôme</a> énumérateur des poids de <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4fc55753007cd3c18576f7933f6f089196732029.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.766ex; height:2.176ex;" alt="{\displaystyle C}" loading="lazy">. L'<a href="Identit%C3%A9_de_MacWilliams" title="Identité de MacWilliams">identité de MacWilliams</a> donne alors celui de <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \scriptstyle C^{\bot }}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \scriptstyle C^{\bot }}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/3e66843f3d59dc4f7768effbd1e644d8528a9c4d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.474ex; height:2.176ex;" alt="{\displaystyle \scriptstyle C^{\bot }}" loading="lazy"> d'où on extrait simplement la distance minimale de ce dernier.

<div class="mw-heading mw-heading3"><h3 id="Code_produit">Code produit</h3></div>

L'<a href="Alg%C3%A8bre_lin%C3%A9aire" title="Algèbre linéaire">algèbre linéaire</a> offre de multiples autres techniques compatibles avec les codes. Le <a href="Produit_tensoriel" title="Produit tensoriel">produit tensoriel</a> est un exemple. À deux <a href="Espace_vectoriel" title="Espace vectoriel">espaces vectoriels</a>, il en associe un troisième <a href="Isomorphisme" title="Isomorphisme">isomorphe</a> aux applications linéaires du premier espace dans le deuxième.

<ul><li>Si C0 (resp. C1) est un code linéaire de paramètre [n0, k0, d0] (resp. [n1, k1, δ1]), alors le produit tensoriel des deux codes est un code de paramètre [n0.n1, k0.k1, δ0.δ1]. Ce code est appelé code produit de C0 et C1.</li></ul>

Il permet de corriger toute configuration comportant moins de δ0.δ1/4 erreurs.

<div class="mw-heading mw-heading2"><h2 id="Traitement_des_erreurs">Traitement des erreurs</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Détection">Détection</h3></div>

La technique la plus simple de traitement des erreurs se limite à une validation. Si le message n'est pas élément du code, alors il est déclaré faux. En général, une nouvelle demande de transmission est la technique de correction.

La méthode la plus fréquemment utilisée consiste à adjoindre au message un ou plusieurs bits de contrôle correspondant à la somme dans le corps fini des coefficients du message. Cette technique est l'analogue de la <a href="Preuve_par_neuf" title="Preuve par neuf">preuve par neuf</a>.

Quitte à augmenter le nombre de bits de contrôle, cette méthode peut accroitre son niveau de fiabilité. Si la probabilité est suffisamment forte pour supposer qu'une seule erreur est à même de se glisser dans le message, alors un bit de contrôle remplit la condition.

Dans le cas d'un unique bit de contrôle, alors les paramètres du code sont [n, n - 1, 2]. Un tel code ne peut pas procéder à la correction de l'erreur par lui-même. En effet pour chaque erreur, il existe n - 1 points du code qui sont proches. Des informations supplémentaires sont nécessaires pour une auto-correction.

L'implémentation est simple, le calcul de l'image du message par la matrice de contrôle fournit l'information. Si l'image est nulle, alors le message correspond à un code et il est sans erreur. Sinon, une erreur est déclarée.

<div class="mw-heading mw-heading3"><h3 id="Correction">Correction</h3></div>

La question est ici traitée uniquement dans le cas des codes systématiques. Non seulement c'est la solution considérée par l'industrie, mais de plus, toute autre configuration est équivalente à celle-là.

Dans un premier temps, il est possible de considérer uniquement le problème au <a href="Vecteur_nul" title="Vecteur nul">vecteur nul</a>. Le message reçu possède donc comme k premières coordonnées 0 et des bits de contrôle c non tous nuls. Cette situation correspond à une erreur, car l'image du vecteur nul par la matrice génératrice donne le vecteur nul et donc les bits de contrôle sont tous nuls pour un code ayant ses k premières coordonnées nulles.

La correction correspond au message m de plus petit poids de Hamming et ayant pour image par la matrice de contrôle -H.c. Si le nombre d'altérations ayant généré le vecteur (0, c) est inférieur à (δ - 1)/2, alors il existe un unique m tel que H.m = -H.c.

Ici, H.c désigne par abus le vecteur H.(0,c). Le code associé est m - c et le message initial est m. On vérifie de fait que H.(m - c) = 0 et m - c est un code. Il est alors possible, à chaque valeur de H.c, d'associer une correction m.

<ul><li>La valeur H.(0,c) où H est une matrice de contrôle systématique et c un ensemble de bits de contrôle non nuls est appelée un syndrome.</li></ul>

Dans le cas général, si l est un message reçu qui n'est pas élément du code, son image par la matrice de contrôle est une valeur correspondant à un H.c donné. Il apparait que m est la plus petite correction à appliquer à l pour obtenir un code. En effet, H(l + m) est égal à H.c - H.c et la minimalité est une conséquence du paragraphe précédent.

La détermination de la valeur m pour un H.c dépend largement du choix du code. Il correspond au problème classique couvert par l'<a href="Optimisation_lin%C3%A9aire" title="Optimisation linéaire">optimisation linéaire</a>. Dans la pratique, il est rare que de telles méthodes soient employées. Soit les bits de contrôles sont en nombre réduits, et la <a href="Combinatoire" title="Combinatoire">combinatoire</a> est réduite, soit l'espace est vaste et le code dispose d'autres propriétés souvent polynomiales et décrite dans l'article <a href="Code_cyclique" title="Code cyclique">code cyclique</a>.

L'implémentation, dans la mesure où l'espace des bits de contrôle est réduit est en général réalisée par une <a href="Table_de_hachage" title="Table de hachage">table de hachage</a>. Cette table établit une <a href="Bijection" title="Bijection">bijection</a> entre chaque syndrome et le message de poids minimal ayant pour image par la matrice de contrôle le syndrome.

<ul><li>Une implémentation de la correction à l'aide d'une table de hachage fournissant une bijection entre les syndromes et les messages de poids minimal est appelée un décodage par syndrome.</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Voir_aussi">Voir aussi</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Bibliographie">Bibliographie</h3></div>

<ul><li><abbr class="abbr indicateur-langue" title="Langue : anglais">(en)</abbr> <a href="Jessie_MacWilliams" title="Jessie MacWilliams">Jessie MacWilliams</a> et <a href="Neil_Sloane" title="Neil Sloane">Neil Sloane</a>, The Theory of Error-Correcting Codes, <a href="Elsevier_(%C3%A9diteur)" class="mw-redirect" title="Elsevier (éditeur)">North-Holland</a>, 1977 (<a href="International_Standard_Book_Number" title="International Standard Book Number">ISBN</a> 978-0-44485009-6)</li>

<li>A. Spătaru, Fondements de la théorie de la transmission de l'information, <a href="PPUR" class="mw-redirect" title="PPUR">PPUR</a>, 1987 (<a href="International_Standard_Book_Number" title="International Standard Book Number">ISBN</a> 978-2-88074133-4)</li>

<li><a href="Michel_Demazure" title="Michel Demazure">Michel Demazure</a>, <cite class="italique">Cours d'algèbre : primalité, divisibilité, codes</cite> [détail des éditions]<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Cours+d%27alg%C3%A8bre&rft.stitle=primalit%C3%A9%2C+divisibilit%C3%A9%2C+codes&rft.aulast=Demazure&rft.aufirst=Michel&rfr_id=info%3Asid%2Ffr.wikipedia.org%3ACode+lin%C3%A9aire"></li></ul>

<div class="mw-heading mw-heading3"><h3 id="Liens_externes">Liens externes</h3></div>

<ul><li><a rel="nofollow" class="external text" href="http://zanotti.univ-tln.fr/cd/chapter3.html">Code correcteur C.I.R.C</a> par J.P. Zanotti, <a href="Universit%C3%A9_de_Toulon" title="Université de Toulon">université de Toulon</a></li>

<li><a rel="nofollow" class="external text" href="http://www.univ-lille1.fr/bustl-grisemine/pdf/articles/A1998-14.pdf">L'algèbre et la correction des erreurs</a> par Dany-Jack Mercier, <a href="Universit%C3%A9_Antilles-Guyane" class="mw-redirect" title="Université Antilles-Guyane">université Antilles-Guyane</a></li>

<li><a rel="nofollow" class="external text" href="http://www.math.u-bordeaux.fr/~zemor/codes06.pdf">Code Linéaire</a> par G. Zemor, <a href="Universit%C3%A9_Bordeaux_I" class="mw-redirect" title="Université Bordeaux I">université Bordeaux I</a></li>

<li>Christine Bachoc, « <a rel="nofollow" class="external text" href="https://www.math.u-bordeaux.fr/~kbelabas/teach/Agreg/code.pdf"><cite style="font-style:normal;">Cours de code</cite></a> », sur <a href="Universit%C3%A9_Bordeaux_I" class="mw-redirect" title="Université Bordeaux I">université Bordeaux I</a>, 2004-2005</li>

<li><a rel="nofollow" class="external text" href="http://agreg-maths.univ-rennes1.fr/documentation/docs/codes.pdf">Code correcteur</a> par M. Coste, A. Paugam, R. Quarez, <a href="Universit%C3%A9_Rennes-I" title="Université Rennes-I">université de Rennes</a></li></ul>

</div>

<ul id="bandeau-portail" class="bandeau-portail"><li> Portail des mathématiques </li> <li> Portail de l'informatique théorique </li> </ul></div><div><div class="zim-footer">

Cet article est issu de <a class="external text" title="Dernière modification le 2022-07-10" href="https://fr.wikipedia.org/wiki/?title=Code_lin%C3%A9aire&oldid=195216298">Wikipédia</a>. Sauf mention contraire, le texte est disponible sous <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.fr">Creative Commons Attribution-Share Alike 4.0</a>. Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.

</div>

</div></div>

</div>

</main>

</div>

</body></html>